package 双指针法;

import com.alibaba.fastjson.JSON;
import common.GeneralFunction;

import java.util.*;

public class No18四数之和 {

    /**
     * 给定一个包含 n 个整数的数组 nums 和一个目标值 target，
     * 判断 nums 中是否存在四个元素 a，b，c 和 d ，
     * 使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
     * 注意：
     * 答案中不可以包含重复的四元组。
     *
     * 示例：
     * 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
     * 满足要求的四元组集合为：
     * [
     *   [-1,  0, 0, 1],
     *   [-2, -1, 1, 2],
     *   [-2,  0, 0, 2]
     * ]
     */
    private List<List<Integer>> lists=new ArrayList<>();
    private Set<List<Integer>> listSet=new HashSet<>();
    private int[] arr;
    private int target;

    //超时解法,不推荐 根据三数之和的经验,应该先排序再计算
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if(nums.length<4){
            return lists;
        }
        this.arr=nums;
        this.target=target;
        dg(0,new ArrayList<>(),0,0);
        return new ArrayList<>(listSet);
    }

    private void dg(int count,List<Integer> path,int sum,int index){

        if(count==4){
            if(sum==target){
                Collections.sort(path);
                listSet.add(path);
            }
            return;
        }

        if(index>=arr.length){
            return;
        }

        //不选自己
        dg(count,new ArrayList<>(path),sum,index+1);
        //从自己开始
        List<Integer> newList = new ArrayList<>();
        newList.add(arr[index]);
        dg(1,newList,arr[index],index+1);
        //选自己
        path.add(arr[index]);
        dg(count+1,path,sum+arr[index],index+1);
    }

    //四数之和 用两个for转为双指针
    public List<List<Integer>> fourSumGood(int[] nums, int target) {

        if(nums.length<4){
            return new ArrayList<>();
        }
//        List<List<Integer>> lists=new ArrayList<>();
        Set<List<Integer>> listSet=new HashSet<>();
        Arrays.sort(nums);
        System.out.println(JSON.toJSONString(nums));

        //[0,1,2,3]
        for (int i = 0; i < nums.length-3; i++) {

            for (int j = i+1; j < nums.length - 2; j++) {

                int left=j+1;
                int right=nums.length-1;
                //先算差值
                int sub=target-nums[i]-nums[j];
                //[left]+[right]==sub
                /**
                 * 这里可以提前剪枝,如果sub为负数,那么后面就可以不用继续了,因为两个数就已经大于了
                 */
//                if(sub<0){
//                    //不该,因为target可能是负数
//                    continue;
//                }

                while (left<right){

                    if(nums[left]+nums[right]==sub){
                        listSet.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        //符合条件
                        left++;
                        right--;
                        //同时减减并过滤相同的,因为现在两数已经相等,两个下标必须做出改变
                        //需要过滤相同的
                        while (right>left&&nums[right]==nums[right+1]){
                            right--;
                        }
                        while (left<right&&nums[left]==nums[left-1]){
                            left++;
                        }
                    }else if(nums[left]+nums[right]<sub){
                        //小了 left++
                        left++;
                    }else{
                        //大了 right--
                        right--;
                    }

                }

            }

        }

        return new ArrayList<>(listSet);

    }

    public static void main(String[] args) {
        int[] arr={1,-2,-5,-4,-3,3,3,5};
        GeneralFunction generalFunction=new GeneralFunction(No18四数之和.class,arr,-11);
        generalFunction.runAllMethod();
    }

}
